package _05_genList;

public class GenList<T> {
    
    // 头指针，指向头结点
    public GenNode<T> head;
    
    // 构造空广义表，表名为null
    public GenList() {
        this.head = new GenNode<T>(null, null, null);
    }
    
    // 构建空广义表，data指定表名
    public GenList(T data) {
        this.head = new GenNode<T>(data, null, null);
    }
    
    // 构造广义表，data指定表名，atoms[]指定原子初值，构造的线性表
    public GenList(T data, T[] atoms) {
        this.head = new GenNode<T>(data, null, null);
        GenNode<T> rear = this.head;
        for (int i = 0; i < atoms.length; i++) {
            rear.next = new GenNode<T>(atoms[i], null, null);
            rear = rear.next;
        }
    }
    
    public String toString() {
        return this.toString(this);
    }
    
    public String toString(GenList<T> genlist) {
        String str = (genlist.head.data == null ? "" : genlist.head.data.toString()) + "(";
        for (GenNode<T> p = genlist.head.next; p != null; p = p.next) {
            str += toString(p) + (p.next != null ? ", " : "");
        }
        return str + ")";
    }

    private String toString(GenNode<T> p) {
        // TODO Auto-generated method stub
        if (p == null) {
            return null;
        }
        return p.child == null ? p.data.toString() : toString(p.child);
    }
    
    // 返回广义表长度
    public int size() {
        int size = 0;
        for (GenNode<T> p = this.head.next; p != null; p = p.next) {
            size++;
        }
        return size;
    }
    
    // 返回广义表深度，递归方法
    public int depth() {
        int maxDepth = 1;
        for (GenNode<T> p = this.head.next; p != null; p = p.next) {
            int depth = 1;
            if (p.child != null) {
                depth += p.child.depth();
                if (depth > maxDepth) {
                    maxDepth = depth;
                }
            }
        }
        return maxDepth;
    }
    
    // 插入原子x作为第i个结点，x != null，返回插入的原子结点
    // 对i容错，若i < 0，则头插入；若i > 长度，则尾插入。
    public GenNode<T> insert(int i, T x) {
        if (x == null) {
            throw new NullPointerException("x == null");
        }
        if (i < 0) {
            i = 0;
        }
        GenNode<T> p = this.head;
        for (int j = 0; p.next != null && j < i; j++) {
            p = p.next;
        }
        GenNode<T> q = new GenNode<T>(x, null, p.next);
        p.next = q;
        return q;
    }
    
    // 尾插入原子x
    public GenNode<T> insert(T x) {
        if (x == null) {
            throw new NullPointerException("x == null ");
        }
        GenNode<T> p = null;
        for (p = this.head; p.next != null; p = p.next);
        GenNode<T> q = new GenNode<T>(x, null, p.next);
        p.next = q;
        return q;
    }
    
    // 插入子表glist作为第i个结点，genlist != null，返回插入的子表结点。
    // 在插入的子表结点中，datad存储genlist子表表名，child引用genlist子表对象，
    // 若genlist是this中的子表，则genlist成为共享子表。genlist != this，不使this成为递归表。
    public GenNode<T> insert(int i, GenList<T> genlist) {
        if (genlist == null || this == genlist) {
            return null;
        }
        // front指向头结点
        GenNode<T> front = this.head;
        // 寻找第i-1个或最后一个结点
        for (int j = 0; front.next != null && j < i; j++) {
            front = front.next;
        }
        // 在front之后插入子表结点，有表名，child指向（引用）genlist子表，可共享
        front.next = new GenNode<T>(genlist.head.data, genlist, front.next);
        return front.next;
    }
    
    // 尾插入子表genlist
    public GenNode<T> insert(GenList<T> genlist) {
        if (genlist == null || this == genlist) {
            return null;
        }
        GenNode<T> front = this.head;
        while (front.next != null) {
            front = front.next;
        }
        front.next = new GenNode<T>(genlist.head.data, genlist,front.next);
        return front.next;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("测试toString()方法：");
        Integer[] arr0 = {1, 2, 3, 4, 5, 6};
        GenList<Integer> genlist0 = new GenList<Integer>(0, arr0);
        genlist0.head.next.child = new GenList<Integer>(9, arr0);
        genlist0.head.next.child.head.next.child = new GenList<Integer>(99);
        System.out.println(genlist0);
        System.out.println("测试size()方法：");
        System.out.println(genlist0.size());
        System.out.println("测试depth()方法：");
        System.out.println(genlist0.depth());
        System.out.println("测试insert(int i, T x)方法：");
        System.out.println(genlist0.insert(2, 200));
        System.out.println(genlist0);
        System.out.println("测试insert(int i, GenList<T> genlist)方法：");
        GenList<Integer> genlist1 = new GenList<Integer>(30, arr0);
        System.out.println(genlist0.insert(3, genlist1));
        System.out.println(genlist0);
    }

}
